package two.chapter_1.c1_1;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Ex1_1_27 {
    private static int count;

    public static void main(String[] args) {
        count = 0;
        StdOut.println(binomial(2, 1, 0.25));


        StdOut.println(betterbinomialproxy(2, 1, 0.25));
        //StdOut.println("count:"+count);
    }


    public static double binomial(int N, int k, double p) {
        // count++;
        if (N == 0 && k == 0) {
            return 1.0;
        }
        if (N < 0 || k < 0) {
            return 0.0;
        }
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }

    private static double a[][];


    public static double betterbinomialproxy(int N, int k, double p) {

        a = new double[N + 1][k + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= k; j++) {
                a[i][j] = -1;
            }

        }
        return betterbinomial(N, k, p);
    }

    public static double betterbinomial(int N, int k, double p) {
        if (N == 0 && k == 0) {
            return 1.0;
        }
        if (N < 0 || k < 0) {
            return 0.0;
        }

        if (a[N][k] == -1) {
            a[N][k] = (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
        }
        return a[N][k];
    }


}
